package leetcode;

import java.util.HashMap;

/*
 * 想明白一点：|nums[i] - nums[j]| == k，就无所谓i和j的谁前谁后了；
进而再明白一点：无所谓i和j的先后顺序了，那i和j位置的数值只要相差k就可以了，也就是位置压根儿就无所谓了，只要有两个数，他们的差值是k就可以了；
最后再想明白一点：我们把每个数值出现的次数统计出来，数值间的差值只要是k，我们就记录一下；比如数值v有m个，数值v+k有n个，
那么满足差值为k的数对儿就有m*n个
（乘法原.理)
 */
public class leetcode2006 {
	public static void main(String []args) {
	int	nums[] = {1,2,2,1};
	int k = 1;
	System.out.println(solution2(nums,k));
	}
//	public static int backTracing(int arr[],int k,int start,int next) {
//		if(Math.abs(arr[next]-arr[start])==k) {
//			return 1;
//		}
//		else {
//			return 0;
//		}
//		
//	}
	// 暴力 解法 : 
	public static int solution(int arr[],int k) {
		int ans=0;
		for(int i = 0;i < arr.length;i++) {
			for(int j =i+1; j<arr.length;j++) {
				if(Math.abs(arr[i]-arr[j])==k) {
					ans++;
				}
			}
		}
		return ans;
	}
	//  计数法  与顺序 无关  只要 存在 两个值的 差 为 k 就行了 与顺序 无关 就容易了
	public static int solution1(int arr[],int k) {
		int temp[]= new int [101];
		for(int value : arr) {
			temp[value]++;
		}
		int ans=0;
		for(int i=1;i + k<=100;i++) {
			ans+=temp[i] * temp[i+k];
		}
		return ans;
	}
	// 也是 计数 法  不过 这个 计数  工具 是用 hashMap替代 数组
	public static int solution2(int arr[],int k) {
		HashMap<Integer,Integer> map=new HashMap<>();
		//map.getOrDefault(key, defaultValue)
		for(int value : arr) {
			if(map.containsKey(value))
				map.put(value,map.get(value)+1);
			else
				map.put(value, 1);
		}
		int ans=0;
		for(int key: map.keySet()) {
			if(map.containsKey(key+k))
			ans+=map.get(key) * map.get(key+k);
		}
		return ans;
	}
}
